//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 10⁴ 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 栈 字符串 动态规划 👍 1893 👎 0

package leetcode.editor.cn;

import java.util.Stack;

class LongestValidParentheses {
    public static void main(String[] args) {
        Solution solution = new LongestValidParentheses().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int longestValidParentheses(String s) {
            if (s.length() == 0 || s == null) return 0;
            Stack<Character> stack = new Stack<>();
            int res = 0;
            int max = 0;
            for (char c : s.toCharArray()) {
                if (c == '(') {
                    if (!stack.isEmpty() && stack.peek() == '(') max = 0;
                    stack.push('(');
                }

                else if (c == ')') {
                    if (!stack.isEmpty() && stack.peek() == '(') {
                        stack.pop();
                        max += 2;
                        res = Math.max(max, res);
                    }else if (stack.isEmpty()) max = 0;
                }
            }

            return res;
        }*/

        // dp
        // 如果s[i] = ')' , s[i-1] = '(' , dp[i] = dp[i - 2] + 2;
        // 如果s[i] = ’)‘, s[i - 1] = ')' , dp[i - dp[i - 2] - i] = '(', dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2]  + 2
        /*public int longestValidParentheses(String s) {
            int maxAns = 0;
            int[] dp = new int[s.length()];
            char[] array = s.toCharArray();
            for (int i = 1; i < array.length; i++) {
                if (array[i] == ')') {
                    if (array[i - 1] == '(') {
                        dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                    } else if (i - dp[i - 1] > 0 && array[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                }
                maxAns = Math.max(maxAns, dp[i]);
            }
            return maxAns;
        }*/

        // 栈
        /*public int longestValidParentheses(String s) {
            // 存储下标，栈底始终为最后一个没有被匹配的的右括号的下标
            Stack<Integer> stack = new Stack<>();
            // 初始化-1进去，满足一开始栈为空的情况
            stack.push(-1);
            int res = 0;
            char[] array = s.toCharArray();
            for (int i = 0; i < array.length; i++) {
                if (array[i] == '(') {
                    stack.push(i);
                } else if (array[i] == ')') {
                    stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                    } else {
                        res = Math.max(res, i - stack.peek());
                    }
                }
            }
            return res;
        }*/

        // 不开辟额外的空间
        public int longestValidParentheses(String s) {
            int left = 0, right = 0, maxLength = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') left++;
                else right++;

                if (left == right) maxLength = Math.max(maxLength, 2 * right);
                else if (right > left) left = right = 0;
            }

            left = right = 0;
            for (int i = s.length() - 1; i > 0; i--) {
                if (s.charAt(i) == '(') left++;
                else right++;

                if (left == right) maxLength = Math.max(maxLength, 2 * left);
                else if (left > right) left = right = 0;
            }

            return maxLength;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
